/**
 * 桶排序算法
 * 时间复杂度 O(n + m)
 * 空间复杂度 O(n + m)
 */
public class BucketSortAlgorithm {
    /**
     * 桶排序
     * @param array 待排序数组： 假定元素均为大于等于 0 的 int
     * @param max 数组中的最大元素
     */
    public static void bucketSort(int[] array, int max){
        int[] bucket = new int[max + 1];
        for (int value : array) {
            bucket[value]++;
        }
        // 直接从桶中恢复排序后的数组不能保证排序的稳定性
        // 下面的做法保证排序的稳定性
        int[] temp = new int[array.length];
        for(int i = 0; i < temp.length; i++){
            temp[i] = array[i];                     // 将待排序的数组拷贝到临时数组
        }
        for(int i = 1; i < bucket.length; i++){
            bucket[i] = bucket[i - 1] + bucket[i];  // bucket[i] 中记录着元素 i + 1 的开始位置
        }
        for(int i = temp.length - 1; i >= 0; i--){
            array[bucket[temp[i]] - 1] = temp[i];   // bucket[i] - 1 为元素 i 的结束位置
            bucket[temp[i]]--;                      // 将桶中的数取出来
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{8, 9, 2, 6, 5, 4, 3, 2, 1};
        for(int value : array){
            System.out.print(value + " ");
        }
        System.out.println();
        BucketSortAlgorithm.bucketSort(array, 9);
        for(int value : array){
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
